import util.MaxHeap;

/**
 * The class implementing the exhaustive nearest-neighbor search
 */
public class Brute extends NN
{
	private MaxHeap kNN;
	private int k;

	/**
	 * 
	 * @param DataBase
	 */
	public Brute(Point DataBase[])
	{
		super(DataBase);		
		k = 1;
	}

	/**
	 * 
	 * @param DataBase
	 * @param k the number of returned nearest neighbor by this exhaustive search
	 */
	public Brute(Point DataBase[], int k)
	{
		super(DataBase);
		this.k = k;
	}

	/**
	 * @param q the query point
	 * @return an array of ID and distance to query returned as the nearest neighbor(s)
	 */
	public SortingElement[] Query(Point q)
	{
		kNN = new MaxHeap();
		Double upperBound = DataBase[0].Distance(q);
		// Insert the first point to heap
		kNN.insert(new SortingElement(0, upperBound));
		Double distance;

		// Insert the first k points to heap
		for (int i = 1; i < k; i++)
		{
			distance = DataBase[i].Distance(q);
			kNN.insert(new SortingElement(i, distance));
		}

		upperBound = ((SortingElement)kNN.max()).value;

		// For the rest of the points in database, insert to heap if it's distance to q is smaller than the worst distance in the heap
		for (int i = k; i < pointCount; i++)
		{
			distance = DataBase[i].Distance(q);
			if (distance < upperBound)
			{
				kNN.removeMax();
				kNN.insert(new SortingElement(i, distance));
				upperBound = ((SortingElement)kNN.max()).value;
			}		
		}
		
		// Extract all the element in the heap to an array to be returned
		SortingElement[] ref = new SortingElement[k];
		int i = k-1;
		while (!kNN.isEmpty()) ref[i--] = (SortingElement)kNN.removeMax();
	
		return ref;
	}
}
